public class Ghost {
    public Position pos;

    public Ghost(int x, int y) { pos = new Position(x, y); }

    // BFS找下一步
    public Position nextStep(Position target, char[][] map) {
        int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
        int h = map.length, w = map[0].length;
        boolean[][] visited = new boolean[h][w];
        Position[][] prev = new Position[h][w];
        MyQueue<Position> q = new MyQueue<>(h*w);
        q.enqueue(pos); visited[pos.y][pos.x] = true;

        while (!q.isEmpty()) {
            Position cur = q.dequeue();
            if (cur.x == target.x && cur.y == target.y) break;
            for (int[] d : dir) {
                int nx = cur.x + d[0], ny = cur.y + d[1];
                if (nx >= 0 && nx < w && ny >= 0 && ny < h &&
                    map[ny][nx] != '#' && !visited[ny][nx]) {
                    q.enqueue(new Position(nx, ny));
                    visited[ny][nx] = true;
                    prev[ny][nx] = cur;
                }
            }
        }
        // 回溯找第一步
        Position step = target;
        while (prev[step.y][step.x] != null && !prev[step.y][step.x].equals(pos)) {
            step = prev[step.y][step.x];
        }
        return step;
    }
}